/*
 * MaximalShift.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "MaximalShift.h"

#include "../Structures/Config.h"
#include "../Utils/MaximalShiftQuickSort.h"

#define ASIZE 255
#define MAX(a, b) (a > b) ? a : b

MaximalShift::MaximalShift()
{

}

MaximalShift::~MaximalShift()
{

}

std::string MaximalShift::getName()
{
	return "Maximal Shift";
}

int* minShift;


/* Construct an ordered pattern from a string. */
void MaximalShift::orderPattern(std::string pattern, patStruct *pat)
{
	int patternSize = pattern.size();

	int i;

	for (i = 0; i <= patternSize; ++i)
	{
		pat[i].loc = i;
		pat[i].c = pattern[i];
	}

//	MaximalShiftQuickSort::sort(pat, patternSize, minShift);
}

void MaximalShift::computeMinShift(std::string pattern)
{
	int patternSize = pattern.size();

	int j;

	for (int i = 0; i < patternSize; ++i)
	{
		for (j = i - 1; j >= 0; --j)
		{
			if (pattern[i] == pattern[j])
			{
				break;
			}
		}
		minShift[i] = i - j;
	}
}

searchResult MaximalShift::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	minShift = new int[patternSize];

	int i, j;

	patStruct* pat = new patStruct[patternSize + 1];

	/* Preprocessing */
	computeMinShift(pattern);
	orderPattern(pattern, pat);
	int* qsBc = preQsBc(pattern);
//	int* adaptedGs = preAdaptedGs(pattern, pat);

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = 0;
		while (i < patternSize && pattern[i] == text[i + j]/*pat[i].c == text[j + pat[i].loc]*/)
		{
			++i;
		}
		if (i >= patternSize)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
		}
		j += /*MAX(adaptedGs[i],*/ qsBc[text[j + patternSize]]/*)*/;
	}

	return result;
}
